package com.lw.leetcode.linked.c;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * Created with IntelliJ IDEA.
 * linked
 * 432. 全 O(1) 的数据结构
 *
 * @author liw
 * @version 1.0
 * @date 2021/11/30 16:31
 */
public class AllOne {

    public static void main(String[] args) {
        AllOne test = new AllOne();

        // [null,null,null,null,null,null,null,null,null,"a",null,"c","c"]
        test.inc("a");
        test.inc("b");
        test.inc("b");
        test.inc("c");
        test.inc("c");
        test.inc("c");
        test.dec("b");
        test.dec("b");
        System.out.println(test.getMinKey());
        test.dec("a");
        System.out.println(test.getMaxKey());
        System.out.println(test.getMinKey());
    }

    private Node head;
    private Node end;
    private Map<String, Integer> countMap;
    private Map<String, Node> nodeMap;

    public AllOne() {
        nodeMap = new HashMap<>();
        countMap = new HashMap<>();
        head = new Node(-1);
        end = new Node(-1);
        head.next = end;
        end.pre = head;
    }

    public void inc(String key) {
        Integer count = countMap.get(key);
        if (count == null || count == 0) {
            countMap.put(key, 1);
            Node next = head.next;
            if (next.var == 1) {
                next.set.add(key);
            } else {
                next = new Node(1);
                next.set.add(key);
                add(head, next);
            }
            nodeMap.put(key, next);

        } else {
            countMap.put(key, count + 1);
            Node node = nodeMap.get(key);
            Node next = node.next;
            if (next.var == count + 1) {
                next.set.add(key);
            } else {
                next = new Node(count + 1);
                next.set.add(key);
                add(node, next);
            }
            nodeMap.put(key, next);
            node.set.remove(key);
            if (node.set.isEmpty()) {
                remove(node);
            }
        }
    }

    public void dec(String key) {
        Integer count = countMap.get(key);
        if (count == null || count == 0) {
            return;
        }
        countMap.put(key, count - 1);
        Node node = nodeMap.get(key);
        Node pre = node.pre;
        if (count > 1) {
            if (pre.var == count - 1) {
                pre.set.add(key);
                nodeMap.put(key, pre);
            } else {
                Node item = new Node(count - 1);
                item.set.add(key);
                add(pre, item);
                nodeMap.put(key, item);
            }
        } else {
            nodeMap.put(key, null);
        }
        node.set.remove(key);
        if (node.set.isEmpty()) {
            remove(node);
        }
    }

    public String getMaxKey() {
        if (end.pre.pre == null) {
            return "";
        }
        return end.pre.set.iterator().next();
    }

    public String getMinKey() {
        if (head.next.next == null) {
            return "";
        }
        return head.next.set.iterator().next();
    }


    private void add(Node st, Node item) {
        Node next = st.next;
        st.next = item;
        item.next = next;
        next.pre = item;
        item.pre = st;
    }

    private void remove(Node item) {
        Node st = item.pre;
        Node next = item.next;
        st.next = next;
        next.pre = st;
    }

    class Node {
        private int var;
        private Set<String> set = new HashSet<>();
        private Node next;
        private Node pre;

        public Node(int var) {
            this.var = var;
        }
    }

}
